Host devices such as computers, laptops, personal video recorders (PVRs), MP3 players, game consoles, servers, set-top boxes, digital cameras, and/or other electronic devices often need to store a large amount of data. Storage devices such as hard disk drives (HDD) may be used to meet these storage requirements.
A hard disk controller (HDC) communicates with the storage device and the host system. The HDC manages interaction between the storage device and the host system. Communication between the host system and the HDC is usually provided using one of a variety of standard I/O bus interfaces. Typically, when data is read from a storage device, a host system sends a read command to the HDC, which stores the read command into a buffer memory. Data is read from the storage device and stored in the buffer memory.
Linked lists (e.g. a queue of fiber channel frames) can manage the flow of data from the host system to the storage device. Referring now to FIG. 1, an exemplary linked list 10 is shown to include nodes 20-1, 20-2, . . . , and 20-n, referred to collectively as nodes 20. The nodes 20 include previous pointers 30-1, 30-2, . . . , and 30-n, referred to collectively as previous pointers 30, and next pointers 40-1, 40-2, . . . , and 40-n, referred to collectively as next pointers 40. The previous pointers 30 store addresses of nodes including the previous data values in the linked list 10 relative to a current node. The next pointers 40 store addresses of nodes containing the next data values in the linked list 10 relative to a current node. The linked list 10 permits the nodes 20 to be stored at noncontiguous locations in the buffer memory.
A ground 50 represents a null or zero address stored in the next pointer 40-n. The null address indicates that the node 20-n is a final node in the linked list 10. Similarly, the previous pointer 30-1 stores a zero address value indicating that no previous nodes exist in the linked list 10.
Conventionally, a controller processes and stores linked lists in the buffer memory in the order the data is transmitted from the host system. An HDD system may require the linked lists to be reordered by an element contained in the node. The HDD system may also need to search the linked list to locate an element contained within the nodes. Typically, firmware (e.g. instructions stored in ROM, EPROM, and EEPROM) of a processor of the HDD system performs the sort and/or search operations on the linked list. Firmware accesses the nodes of a linked list sequentially in the buffer memory.